'''
https://leetcode.cn/problems/recover-binary-search-tree/description/
'''


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def recoverTree(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        stack = []
        cur = root
        prev, x, y = None, None, None
        while cur or stack:
            while cur:
                stack.append(cur)
                cur = cur.left
            cur = stack.pop()
            if prev and cur.val < prev.val:
                y = cur
                if x is None:
                    x = prev
            prev = cur
            cur = cur.right
        x.val, y.val = y.val, x.val

